FIG. 1 shows a prior art computing system 101 that is communicatively coupled to a plurality of Local Area Networks (LANs) and Wide Area Networks (WANs). As observed in FIG. 1, each of LANs 103_1 through 103_4 is a local area network to which the computing system 101 is directly connected. Examples of such local area networks include standard “Layer 2” networks such as IEEE 802.3 based networks (e.g., Ethernet networks) and IEEE 802.11 based networks (e.g., Wireless/WLAN networks).
As depicted in FIG. 1, each of the LANs 103_1 through 103_4 is a subnet within a larger “Layer 3” (e.g., Internet Protocol (IP)) network. Note that at least two separate Layer 3 networks 104_1, 104_2 are observed in FIG. 1 (e.g., a first IP network 104_1 that is separate and isolated from a second IP network 104_2). The computing system is also coupled to WANs 104_3 and 104_4 (noting that each of Layer 3 networks 104_1, 104_2 could also be WANs). The computing system 101 is directly connected to WAN 104_3 and remotely coupled to WAN 104_4.
The computing system 101 contains separate interfaces for communication into the subnets 103_1 through 103_4 and WANs 104_3 and 104_4. That is, interfaces 102_1 through 102_4 are interfaces for subnets 103_1 through 103_4, respectively, and, interfaces 102_5 and 102_6 are interfaces for WANs 104_3 and 104_4, respectively. Here, each interface has: 1) an “end point” address (e.g., an IP address) that corresponds to an address of the computing system 101 on a particular network; and, 2) functionality for executing protocols that are specific to the particular network.
Transmitting packets into a particular network is accomplished by submitting payload data to the corresponding interface. The interface and its associated functionality responds by encapsulating the payload data with appropriate protocol information to form a packet for its respective network. The existence of an interface therefore represents the existence of a “network service” in the sense that the computing system maintains functionality for forming packets for transportation within a particular network.
FIG. 1 also shows a routing table 110 within the prior art computing system 101. The routing table identifies, based on an outbound packet's destination address, an appropriate network interface for that packet. In the case of subnets, the routing table also identifies the packet's MAC layer destination address within the subnet. The following discussion illustrates by way of example the manner in which routing table entries are added and used according to the prior art approach. Specifically, FIGS. 2a through 2d pertain to the manner in which entries for subnets 103_1 through 103_4 are added and used. FIGS. 2e through 2g pertain to the manner in which entries for WANs 104_3 and 104_4 are used.
As observed in FIG. 2a, two initial entries are observed 211 and 212 for subnets 103_1 and 103_2—both of which are Ethernet LANs. As observed in FIG. 2a, an entry for a LAN identifies: 1) the LAN's address as a “destination”; and, 2) the LAN's network interface within the system 101. For instance, entry 211 identifies: 1) subnet address 192.168.1 as the destination; and, 2) interface “en_1” which is the interface for subnet 103_1.
As will be observed immediately below by way of example, once a subnet route entry exists, the computing system is able to resolve for specific destination addresses within the subnet. For the routing table state 210a observed in FIG. 2a, when a need to send a packet to a particular end point destination or “host” on either of subnets 103_1 or 103_2 arises, the host's destination address is used as a look up parameter for performing a “longest prefix match” search in the destination address column of the routing table 210a. Thus, for example, if a need arises to send a packet to an end-point within system 105_1 (located on subnet 103_1) having destination address 192.168.1.10, a look-up is performed in the routing table 210a using 192.168.1.10 as a look up parameter. The longest prefix match will hit on entry 211 (since 192.168.1 is a deeper match than the default entry).
The computing system 101 is able to recognize, however, that entry 211 only identifies a subnet (192.168.1) and not a particular host on that subnet (192.168.1.10). As such, as observed in FIG. 2b, the computing system adds another entry 213 in the routing table 210b specifically for the host destination. Entry 213 is referred to as a “route” because it identifies a specific host or end-point destination. The addition of new route 213 is also consistent with the ARP protocol associated with IPv4 subnets in that it includes the additional detail of a specific IP destination address (192.168.110) but, at least initially, only duplicates or “clones” the interface information (en_1) of the subnet network service entry 211.
For new host routes within a subnet, such as route entry 213, the computing system 101 will attempt to further resolve the route 213 for additional destination address information that is specific to the subnet (e.g., a specific MAC layer address within the subnet). Specifically, the computing system 101 will launch an ARP packet into subnet 103_1 to identify the MAC address for the system on subnet 103_1 that includes IP address 192.168.1.10. Because system 105_1 has this end point, the subnet 103_1 will return the Ethernet MAC address of system 105_1.
Upon receipt of the MAC address for system 105_1 from subnet 103_1, the computing system 101 will enter the MAC address for system 105_1 (00:aa:bb:cc:dd:ee) as the next node for entry 213. This state is observed as state 210c in FIG. 2c. Thus, a subsequent look up on destination 192.168.1.10 in the table will return the next node for that destination (i.e., MAC address (00:aa:bb:cc:dd:ee)) and the interface from which a packet sent by computing system should be sent in order to reach that destination (i.e., interface “en_1” 102_1). Thus, the next node column in the routing table (where applicable) identifies, for a specific entry in the routing table's destination column, the appropriate network node that the computing system 101 should send the packet to.
If a need to send a packet to destination address 192.168.2.20 within system 105_2 on subnet 103_2 arises, the same process repeats itself resulting ultimately in new route entry 214 that specifies, as observed in FIG. 2d, the MAC address of system 105_5 (00:11:22:33:44:55) as the next node for that destination and the interface (“en_2” 102_2) from which a packet sent by computing system should be sent in order to reach that destination.
Here, both of entries 213, 214 identify an interface that transmits into a subnet, (specifically, entry 213 identifies interface en_1 which transmits into subnet 103_1 and entry 214 identifies interface en_2 which transmits into subnet 104_1) Properties of an interface that transmits into a subnet include a capability to articulate any one of multiple destination addresses within the header information created by the interface. As a consequence of this property, subnet representations within the routing table typically include multiple entries/destinations for a same subnet interface.
For instance, if additional end-point destinations 192.168.2.11, 192.168.2.12 and 192.168.3.13 existed on subnet 103_2, three additional entries would be observed in FIG. 2d beneath entry 214—one entry for each of these IP addresses that specifies its own unique MAC address. Here, over the course of operation, the subnet interface en_1 102_1 is expected to be able to create header information that includes any one of these MAC addresses as appropriate.
Interfaces for “non subnets” also exist. Examples include an interface for a Virtual Private Network (VPN) and an interface for a Point-to-Point (PPP) link over a physical transport medium (such as PPP over a modem connection or PPP over Ethernet (PPPoE)). Because interfaces such as these, from their own isolated perspective, do not transmit into a subnet—they do not include the ability to identify a range of possible destinations within the header information they construct. As a consequence, the structure of their corresponding representations within the routing table differ from those of a subnet.
FIG. 1 supports some examples. Specifically, assume the WAN_1 interface 102_5 is a PPP interface whose corresponding packets are transmitted over a direct connection to the Internet (WAN_1) 104_3, and, assume the WAN_2 interface 102_6 is a VPN interlace configured to transmit packets to a server 105_6 that provides access to a VPN WAN_2 104_4.
In the case of the PPP interface 102_5, which may be for a PPP over modem connection or a PPP over Ethernet (PPPoE) connection into WAN_1 104_3, the PPP interlace 102_5 encapsulates IP packets destined for transport within the WAN_1 with appropriate PPP headers and forwards them to an access node to WAN_1 (not shown) which strips off the PPP headers and “dumps” the IP packets into WAN_1. The PPP headers created by the interface 102_5 are not capable of uniquely identifying a range of possible destination addresses because all packets created by the PPP interface 102_5 are sent directly to this access node.
The VPN interface 102_6 encapsulates packets for transportation within WAN_2 104_4 with an IP packet whose destination address (10.11.12.13) specifies node 105_6. That is, WAN interface 102_6 is designed to construct a packet that will reach the access node 105_6 to WAN_2. As such, like the PPP interface 102_5, the header information created by the VPN interface 102_6 is not capable of uniquely identifying a range of possible destination addresses because all packets created by the VPN interface 102_6 are sent directly to the WAN_2 access node 105_6.
FIG. 2e shows the presence of a routing table entries 215, 216 for the VPN interface 102_6 and corresponding WAN_1 104_4. Routing table entries for the PPP interface 102_5 and WAN_1 will be discussed in more detail further below. With respect to the VPN, two entries 215, 216 are created in the routing table as observed in FIG. 2e. A first entry 215 lists the IP address of the VPN access node 105_6 (10.11.12.13) as a destination and the subnet gateway 106 (IP address=192.168.1.11) used to reach the access node as a next node that computing system 101 transmits to. A second entry 216 lists the portion of a destination address that identifies WAN_2 (“17/8”) as a destination and identifies the WAN_2 interlace 102_6 as the appropriate interface.
Upon submission of these entries to the routing table, the following operations transpire. WAN_2 has address “17/8” so packets destined for WAN_2 will have an address that begins with “17/8”. For instance, a packet destined for node 105_7 will be labeled 17/8.1.2.3. Submission of this destination address to the routing table results in a hit on entry 216 because that is deepest match amongst the destination addresses listed in the routing table. Entry 216 identifies the WAN_2 interface 102_6. As such, an outbound packet having destination address 17/8.1.2.3 is processed by interface 102_6 which, as discussed previously, includes encapsulation with an IP packet having a destination address that identifies access node 105_6 (10.11.12.13). At this point an IP packet having destination address 10.11.12.13 has been created which causes a second lookup into the routing table.
Destination address 10.11.12.13 will hit on entry 215 which returns the identity of gateway 106 (IP address=192.168.1.11). A lookup on IP address 192.168.1.11 returns a hit on entry 211 which causes, in accordance with the manner in which entries 213 and 214 were created, the addition of an entry 217 for gateway 106 (having MAC address 00:aa:bb:cc:dd:ff) within subnet 103_1. Thus, a lookup on entry 192.168.1.11 ultimately returns the MAC address of gateway 106 and the identity of the en_interface 102_1. Ultimately therefore, the outbound IP packet created by the WAN_2 interface 102_6 having the IP address of the VPN access node 105_6 is encapsulated with Ethernet headers by the en_1 interface 102_1 that specify the MAC address of gateway 106. The Ethernet packet is then transmitted into subnet 103_1. Subsequent packets whose destination address specify network “17/8” will cause an identical chain of processes (except that entry 217 does not need to be created because it now exists in the routing table). In this manner, a destination address is continually resolved until no further resolution of destination addresses and interfaces remain.
FIGS. 2a through 2f also show the presence of a default entry 218. In the prior art approach, the default entry 218 was used as a “catch all” to route packets whose destination addresses did not hit on a more specific entry in the routing table into a particular network. As observed, the default entry 218 also identifies the gateway 106 for subnet 103_1. Thus, as presently observed in FIG. 2f, a packet whose destination address fails to more specifically match to another routing table entry will be forwarded into network 104_1 through gateway 106. As an example, consider a packet whose IP destination address is 1.2.3.4. Submission of this destination address to the routing table results in a deepest match hit on the default entry 218 as compared to the other entries observed in the routing table (in the prior art approach, the default entry was set to 0.0.0.0).
As a result of the hit on the default entry 218, the packet is encapsulated with Ethernet headers by the en_1 interface that specify the MAC address of gateway 106 as the destination. Also, an entry 219 for destination address 1.2.3.4 is entered into the routing table listing the gateway 106 of subnet 103_1 as the next node. Thus, a subsequent submission for destination 1.2.3.4 will hit on entry 219 which returns the IP address of gateway 106 (192.68.1.11) which causes another lookup in the routing table which hits on entry 217. The result of this hit is the transmission of the packet from en_1 into subnet 103_1 encapsulated with the MAC address of gateway 106.
A problem with the prior art approach, however, was that only one default entry was present in the routing table at any given time resulting in, among other problems, the inability of the computing system 101 to transmit packets into all of the networks it was coupled to. For instance, PPP interface 102_5 is only useable if WAN_1 is configured to be the default. Here, recall that the VPN has a specific numeric identifier “17/8” while WAN_1 has no such specific numeric identifier. In the present example being discussed, WAN_1 is the Internet which is a collection of different networks having different numeric identifiers but no single numeric reference identifies the Internet particularly. Thus, packets destined for the Internet essentially have random destination addresses (like 1.2.3.4) which—at least initially—will only hit on the default entry. Thus, in the prior art approach, in order to send packets into network WAN_1 104_3, the default entry had to be changed from the state observed in FIG. 2f to the state observed in FIG. 2g. 
Here, FIG. 2g shows the default entry 220 after it has been changed to WAN_1 (e.g., to configure Internet service for computing system 101). A background process also detected the change and removed entry 219 (because that was presumed valid for a different network). Here, submission of an IP packet destined for the Internet 104_3 having an essentially random destination address (e.g., IP address=5.6.7.8) will hit on the default entry 220 which returns the identity of the PPP interface WAN_1 102_5. The PPP interface appends PPP headers to the IP packet and transmits the PPP packet to the access node for WAN_1 (not shown) which strips off the PPP headers and dumps the packet into the Internet/WAN_1. An entry 221 is created in the routing table for destination address 5.6.7.8 that identifies the WAN_1 interface.
A problem with the prior art approach is that network destinations on different networks which required the use of the default entry to be reached could not be concurrently reached. For instance, if network 104_1 was isolated from the Internet, and another packet to the 1.2.3.4 destination address on network 104_1 was submitted to the routing table observed in FIG. 2f, the packet would improperly be sent into the Internet 104_3 rather than network 104_1 because the default entry 220 no longer points to network 104_1.
Another problem is asymmetric input/output flows. For instance, computing system 101 can receive multiple input streams from network 104_1 via its connection to that network through multiple interfaces en_1 through en_3. Because of the single default entry (e.g., gateway 106), however, input flows arriving to interfaces en_1 through en_3 from beyond their respective subnets 103_1 through 103_3 could only be responded to through the same subnet via the default entry. So, for instance, interface en_1 would transmit to all hosts beyond subnets 103_1 through 103_3 even though interfaces en_1, en_2 and en_3 were receiving packets from these hosts (here, recall that each interface has its own IP address on network 104_1). Interface en_1 would therefore be required to process more than a pro rata share of the traffic being received by system 101 resulting in a potential bottleneck.
Another problem was the inability to handle identical destination addresses on different networks. According to the manner in which entries were added and listed in the routing table, a same destination address would always be sent from the same interface.